using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PhraseCorrector.SpellCore
{
    /* <summary>
     * 提供一系列用于计算相似度的方法。
     * </summary>
     */
    public static class SpellCoefficient
    {
        #region 字串相似度
        
        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算两个字符串的相似度。
        /// </summary>
        /// <param name="s1">第一个字符串。</param>
        /// <param name="s2">第二个字符串。</param>
        /// <returns>返回两个字符串的相似度。</returns>
        public static double Similarity(this string s1, string s2)
        {
            // 通过计算Damerau-Levenshtein距离和Dice系数的较大值来确定字符串的相似度
            //return Math.Max(ComputeDamerauLevenshteinDistance(s1, s2), DiceCoefficient(s1, s2));
            return ComputeDamerauLevenshteinDistance(s1, s2).similay;
            //return DiceCoefficient(s1, s2);
        }
        public static (int distance, double similay) Distance(this string s1, string s2) {
            // 通过计算Damerau-Levenshtein距离和Dice系数的较大值来确定字符串的相似度
            //return Math.Max(ComputeDamerauLevenshteinDistance(s1, s2), DiceCoefficient(s1, s2));
            return ComputeDamerauLevenshteinDistance(s1, s2);
            //return (ComputeDamerauLevenshteinDistance(s1, s2).distance, DiceCoefficient(s1, s2));
        }
        #endregion

        #region  字符相邻程度
        // /////////////////////////////////////////////////////////////////////////////		
        /// <summary>
        /// 基于二元组的Dice系数计算方法。<br />
        /// 一个良好的值应该在0.33或以上，值在0.2以下不是一个好的匹配，从0.2到0.33是可疑的。
        /// </summary>
        /// <param name="input">输入的字符串。</param>
        /// <param name="comparedTo">用于比较的字符串。</param>
        /// <returns>Dice系数，表示两个字符串的相似度。</returns>
        public static double DiceCoefficient(this string input, string comparedTo)
        {
            // 将比较字符串转换为二元组集合
            var compareToNgrams= comparedTo.ToBiGrams();
            // 计算并返回两个二元组集合的Dice系数
            return input.ToBiGrams().DiceCoefficient(compareToNgrams);
        }

        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算两个字符串数组之间的Dice系数。
        /// </summary>
        /// <param name="nGrams">第一个字符串数组，包含一系列n-gram。</param>
        /// <param name="compareToNGrams">第二个字符串数组，包含一系列n-gram。</param>
        /// <returns>返回两个数组的Dice系数。</returns>
        /// <remarks>
        /// Dice系数是一种衡量两个集合相似度的指标，其值介于0到1之间，1表示两个集合完全相同。
        /// 该方法通过计算两个数组的交集元素数量和总元素数量来确定它们之间的相似度。
        /// 如果交集元素数量为0，说明两个数组没有相似的n-gram，直接返回0。
        /// 计算公式为：2 * 交集元素数量 / 总元素数量。
        /// </remarks>
        public static double DiceCoefficient(this string[] nGrams, string[] compareToNGrams)
        {
            // 如果交集元素数量为0，说明两个数组没有相似的n-gram，直接返回0
            // 计算并返回Dice系数，公式为：2 * 交集元素数量 / 总元素数量
            return DiceCoefficientResult(nGrams.Intersect(compareToNGrams).Count(), nGrams.Length + compareToNGrams.Length);
        }

        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算并返回两个数组的Dice系数
        /// </summary>
        /// <param name="matches">交集元素数量</param>
        /// <param name="totalBigrams">总元素数量</param>
        /// <returns>Dice系数</returns>
        public static double DiceCoefficientResult(int matches, double totalBigrams)
        {
            // 如果交集元素数量为0，说明两个数组没有相似的n-gram，直接返回0
            // 计算并返回Dice系数，公式为：2 * 交集元素数量 / 总元素数量
            return (matches== 0)
                ? 0.0d
                : 2 * matches / totalBigrams;
        }
        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 将字符串转换为双字母组（bigram）的数组。
        /// </summary>
        /// <param name="input">待转换的原始字符串。</param>
        /// <returns>包含原始字符串的双字母组的数组。</returns>
        /// <remarks>
        /// 此扩展方法首先通过在输入字符串的前后添加特殊字符来确保能够生成首尾相连的双字母组。
        /// 使用特殊字符是为了避免在生成双字母组时出现边界问题，确保每个字母都能与其他字母形成一组。
        /// </remarks>
        public static string[] ToBiGrams(this string input)
        {
            // 在输入字符串的前后添加特定字符，以确保首尾字符也能形成二元组
            input= SinglePercent + input + SinglePound;

            // 调用ToNGrams函数，将输入字符串转换为长度为2的二元组数组
            return ToNGrams(input, 2);
        }

        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 将输入字符串分割成一系列N-gram片段。
        /// </summary>
        /// <param name="input">待处理的输入字符串。</param>
        /// <param name="nLength">N-gram片段的长度。</param>
        /// <returns>返回包含所有N-gram片段的数组。</returns>
        private static string[] ToNGrams(string input, int nLength)
        {
            // 返回包含所有N-gram片段的数组
            return ToNGramsArg(input, nLength, new string[input.Length - 1]);
        }

        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 辅助函数，用于生成N-gram片段数组。
        /// </summary>
        /// <param name="input">待处理的输入字符串。</param>
        /// <param name="nLength">N-gram片段的长度。</param>
        /// <param name="ngrams">用于存储N-gram片段的数组。</param>
        /// <returns>返回填充了N-gram片段的数组。</returns>
        private static string[] ToNGramsArg(string input, int nLength, string[] ngrams)
        {
            // 遍历字符串，生成N-gram片段
            for (int i= 0; i < input.Length - 1; i++)
                ngrams[i]= input.Substring(i, nLength);

            return ngrams;
        }

        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 定义了一系列与格式化相关的常量字符串。
        /// </summary>
        // 定义一个常量SinglePercent("%").代表前缀字符
        private const string SinglePercent= "%";
        // 定义一个常量SinglePound("#")，代表后缀字符
        private const string SinglePound= "#";

        #endregion

        #region 字符并集相似度
        // /////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// 计算两个字符串之间的Damerau-Levenshtein距离。
        /// Damerau-Levenshtein距离是一种衡量两个字符串之间相似度的指标，表示从一个字符串转换成另一个字符串所需的最少编辑操作次数（包括插入、删除、替换和交换字符）。
        /// </summary>
        /// <param name="s">第一个字符串。</param>
        /// <param name="t">第二个字符串。</param>
        /// <returns 返回一个元组，包含两个值。第一个值是Damerau-Levenshtein距离，第二个值是字符串s到t的相对编辑距离（即编辑距离除以t的长度）。</returns>
        public static (int distance, double similay) ComputeDamerauLevenshteinDistance(string s, string t)
        {
            // 初始化字符串长度和距离矩阵
            int n= s.Length;
            int m= t.Length;
            int[,] d= new int[n + 1, m + 1];
            int[,] p= new int[n + 1, m + 1];

            // 如果其中一个字符串为空，则距离为另一个字符串的长度
            if (n== 0 || m== 0) return (0,0);

            // 初始化矩阵第一行和第一列的值
            for (int i= 0; i <= n; d[i, 0]= i++) ;
            for (int j= 0; j <= m; d[0, j]= j++) ;

            // 动态规划计算每个位置的最小编辑距离
            for (int i= 1; i <= n; i++)
            {
                for (int j= 1; j <= m; j++)
                {
                    // 计算当前字符替换成本
                    int cost= s[i - 1]== t[j - 1] ? 0 : 1;

                    // 更新当前位置的最小编辑距离
                    d[i, j]= Math.Min(
                        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                        d[i - 1, j - 1] + cost);

                    // 如果满足条件，考虑字符交换操作
                    // 尝试进行字符交换优化
                    if (i > 1 && j > 1 && s[i - 1]== t[j - 2] && s[i - 2]== t[j - 1])
                    {
                        d[i, j]= Math.Min(d[i, j], d[i - 2, j - 2] + cost);
                        p[i, j]= 4; // 标记为交换操作
                    }
                }
            }
            // 返回最终的编辑距离和相对编辑距离
            return ( d[n,m],(double)(Math.Max(n, m) - d[n, m]) / Math.Max(n, m));
        }
        #endregion
    }
}
